package leetcode.top100;

import com.sun.xml.internal.messaging.saaj.packaging.mime.util.QDecoderStream;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 给定一个会议时间安排的数组，每个会议时间都会包括开始和结束的时间 [[s1,e1],[s2,e2],…] (si < ei)，为避免会议冲突，同时要考虑充分利用会议室资源，请你计算至少需要多少间会议室，才能满足这些会议安排。
 * <p>
 * 示例 1:
 * <p>
 * 输入: [[0, 30],[5, 10],[15, 20]]
 * 输出: 2
 * 示例 2:
 * <p>
 * 输入: [[7,10],[2,4]]
 * 输出: 1
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/meeting-rooms-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

class Interval {
    int start;
    int end;

    Interval() {
        start = 0;
        end = 0;
    }

    Interval(int s, int e) {
        start = s;
        end = e;
    }
}

public class Code253_MeetingRoomNum {
    public static void main(String[] args) {
        Interval[] intervals = new Interval[3];
        Interval[] intervals2 = new Interval[2];
        intervals[0] = new Interval(0,30);
        intervals[1] = new Interval(5,10);
        intervals[2] = new Interval(15,20);

        intervals2[0] = new Interval(7,10);
        intervals2[1] = new Interval(2,4);
        System.out.println(minMeetingRooms(intervals));
        System.out.println(minMeetingRooms(intervals2));
    }
    /**
     * 思路：
     * 首先按照会议的开始时间进行排序。O(nlogn)。
     * 其次，对排好序的会议进行遍历。设置一个小跟堆，存放会议结束时间。
     * 如果下一个会议的开始时间 < 堆顶(最早结束的会议，还没有开完)，那么需要安排新房间
     */
    public static int minMeetingRooms(Interval[] intervals) {
        if(intervals == null || intervals.length == 0) return 0;
        Arrays.sort(intervals,(m1,m2) -> m1.start - m2.start);
        Queue<Integer> minEndQ = new PriorityQueue<>();
        int rooms = 1;
        minEndQ.add(intervals[0].end);
        for (int i = 1; i < intervals.length; i++) {
            //最早开完会的会议时间，比下一次要开始开会的还迟
            if(intervals[i].start < minEndQ.peek()){
                rooms++;
            }else {
                //否则，说明最早开完的那个会 会议室可以被当前占用。
                minEndQ.poll();
            }
            //当前新的会议的最早结束时间
            minEndQ.add(intervals[i].end);
        }
        return rooms;
    }
}
